//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 
// 👍 283 👎 0


package leetcode.editor.cn1;

//Java：最小的k个数
public class ZuiXiaoDeKgeShuLcof {
    public static void main(String[] args) {
        Solution solution = new ZuiXiaoDeKgeShuLcof().new Solution();
        // TO TEST
        int[] res = solution.getLeastNumbers(new int[]{49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22}, 2);
        for (int re : res) {
            System.out.println("re = " + re);
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            return getLeastNumbersFaster(arr, k);
        }

        public int[] getLeastNumbersBubbling(int[] arr, int k) {
            // 直接对arr进行冒泡排序
            int nlen = arr.length, tmp = -1;
            boolean isSorted = false;
            for (int i = 0; i < nlen; i++) {
                for (int j = 0; j < nlen - i - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        tmp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = tmp;
                    }
                }
            }

            // 排序完毕
            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
                res[i] = arr[i];
            }
            return res;
        }

        public int[] getLeastNumbersFaster(int[] arr, int k) {
            // 直接对arr进行冒泡排序
            int nlen = arr.length, tmp = -1, in = 0, ij = nlen - 1;

            quickSort(arr, in, ij);

            // 排序完毕
            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
                res[i] = arr[i];
            }
            return res;
        }

        public void quickSort(int[] arr, int low, int high) {
            if (low < high) {
                int index = quickSubIndex(arr, low, high);
                quickSort(arr, low, index - 1);
                quickSort(arr, index + 1, high);
            }
        }

        public int quickSubIndex(int[] arr, int low, int high) {
            // 选一个基准值
            int base = arr[low];
            while (low < high) {
                // 先从尾部开始，找到<base的值
                while (low < high && arr[high] >= base) {
                    high--;
                }
                arr[low] = arr[high];

                // 从前往后找，找到>base的值
                while (low < high && arr[low] <= base) {
                    low++;
                }
                arr[high] = arr[low];
            }

            // 此时low == high
            arr[low] = base;
            return low;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
